1774D - Same Count One - CodeForces Solution

#include <iostream>
#include <cstring>
#include <cstdio>
#include <math.h> 
#include <algorithm> 
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>

//using namespace std;
using std::cout;
using std::cin;
using ll = long long;
using ld = long double;

#define newline cout << "\n"
#define print_case(x) cout << "Case #" << x << ":"


ll t; 
const ll size = 1e6+6;
const ll MAX = 1e11;
long long gcd(long long a, long long b) {
	if (a == 0 || b == 0) return a;
	return gcd(b, a%b);
}

long long cnt_size(std::map<long long, std::vector<long long>> &pos, long long color, long long index) {
	long long n = pos[color].size();
	if (n == 0) return 0;
	long long prev = pos[color][index], cnt = 1;
	for (long long i = index+1; i < n; ++i) {
		if ((pos[color][i] - prev) & 1) {
			prev = pos[color][i];
			cnt++;
		}
	}	
	return cnt;
}


long long gauss(long long n) {
	return (n*(n+1))/2;
}

bool work(long long k, long long x, long long mid) {
	if (mid <= k) return gauss(mid) < x;
	else {
		long long result = gauss(k), extra = mid-k;
		result = result + result - k - gauss(k - extra-1);
		return result < x;
	}
}

long long bisearch(long long k, long long x) {
	long long left = 1, right = 2*k;
	while (left+1 < right) {
		long long mid = (left+right)/2;
		if (work(k, x, mid)) left = mid;
		else right = mid;
	}
	return left;
}

void solve1(long long cases) {
	long long n; cin >> n;
	std::vector<long long> a(n);
	std::map<long long, long long> freq;
	for (auto &i: a) {
		cin >> i;
		freq[i]++;
	}
	if (n & 1) cout << "NO\n";
	else {
		std::sort(a.begin(), a.end());
		long long left = n/2-1, right = n-1;
		long long itr = 0;
		bool r = true;
		std::vector<long long> ans;
		while (itr++ < n) {
			if (r) ans.push_back(a[right--]);
			else ans.push_back(a[left--]);
			r = !r;
		}
		
		bool yes = true;	
		for (long long i = 0; i < n; ++i) {
			long long next_idx = i+1, prev_idx = i-1;
			if (i == 0) prev_idx = n-1;
			else if (i == n) next_idx = 0;
			long long cur = ans[i], next = ans[next_idx], prev = ans[prev_idx];
			cout << prev << " " << cur << " " << next << "\n";
			if ((cur > next && cur < prev) || (cur < next && cur > prev) || (cur == prev) || (cur == next)) {
				yes = false;
				cout << "hit\n";
			}
		}
		//	for (long long i = 0; i < n; ++i) cout << ans[i] << " ";
		if (yes) {
			cout << "YES\n";
			for (long long i = 0; i < n; ++i) cout << ans[i] << " ";
		}
		else cout << "NO";
		cout << "\n";
	}
}

void solve2(long long cases) {
	long long n, m; cin >> n >> m;
	std::vector<long long> a(n), b(m);
	for (auto &i: a) cin >> i;
	for (auto &i: b) cin >> i;

	
	//std::sort(a.begin(), a.end());
	long long sum = 0;
	for (long long i = 0; i < m; ++i) {
		long long small = 1e10, index = 0;
		for (long long j = 0; j < n; ++j) {
			if (a[j] < small) {
				small = a[j];
				index = j;
			}	
		}
		a[index] = b[i];
	}
	for (long long i = 0; i < n; ++i) sum += a[i];
	cout << sum << "\n";
	
}

char determine(std::vector<std::string> &grid, long long i, long long j) {
	long long n = grid.size();
	long long zeros = 0, ones = 0;
	if (grid[i][j] == '0') zeros++;
	else ones++;
	if (grid[j][n-i-1] == '0') zeros++;
	else ones++;
	if (grid[n-i-1][n-j-1] == '0') zeros++;
	else ones++;
	if (grid[n-j-1][i] == '0') zeros++;
	else ones++;

	if (zeros == 0 || ones == 0) return '2';
	else if (zeros > ones) return '0';
	else return '1';

}

bool visited[(ll)1e6];
long long idx = 0;
ll dfs(std::vector<long long> grid[], long long node, std::vector<std::vector<long long>> &ans) {
	visited[node] = true;
	long long paths = 0;
	bool end = true;
	for (const auto &child: grid[node]) {
		if (!visited[child]) {
			end = false;
			ans[idx].push_back(child);	
			paths += dfs(grid, child, ans);
		}
	}
	if (end) {
		paths++;	
		idx++;
	}
	return paths;
}

#define alice cout << "Alice\n"
#define bob cout << "Bob\n"


long long mod = 1e9+7;
long long ncr[70][70];
void nCr() {
	ncr[0][0] = 1;
	ncr[1][0] = 1;
	for (ll i = 1; i <= 60; ++i) {
		for (ll j = 0; j <= i; ++j) {
			ncr[i][j] = ncr[i-1][j] + ncr[i-1][j-1];
		}
	}
}

bool work(ll i) {
	std::string s = std::to_string(i);
	ll n = s.size();
	ll left = 0, right = n-1;
	while (left <= right) {
		if (s[left++] != s[right--]) return false;
	}
	return true;
}

long long check(long long d) {
	long double s1 = (1LL+std::sqrt(1+4*2LL*d))/2LL;
	if (s1 < 0 || s1 != std::ceil(s1)) return -1;
	else return (long long)s1;	
}
void print(std::vector<ll> a) {
	for (ll i = 0; i < a.size(); ++i) cout << a[i];
	cout << "\n";
}

bool cmp(std::pair<ll, ll> p1, std::pair<ll, ll> p2) {
	return p1.first <= p2.first;
}

void solve(ll cases) {
	ll n, m; cin >> n >> m;
	std::vector<std::vector<ll>> a(n, std::vector<ll>(m));
	std::map<ll, std::vector<ll>> extras, needs;
	ll sum = 0, target = 0;
	for (ll i = 0; i < n; ++i) {
		for (ll j = 0; j < m; ++j) {
			cin >> a[i][j];
			if (a[i][j] == 1) sum++;
		}
	}
	target = sum/n;
	std::vector<ll> cnts(n, target);
	if (sum % n > 0) {
		cout << -1 << "\n";
		return;
	}
	for (ll i = 0; i < n; ++i) {
		ll row_sum = 0;
		for (ll j = 0; j < m; ++j) {
			if (a[i][j] == 1) row_sum++;
		}
		cnts[i] = row_sum;
	}
	std::vector<std::vector<ll>> ans;
	for (ll j = 0; j < m; ++j) {
		std::queue<ll> supply, demand;
		for (ll i = 0; i < n; ++i) {
			if (cnts[i] > target && a[i][j] == 1) supply.push(i);
			else if (cnts[i] < target && a[i][j] == 0) demand.push(i);
		}
		while (!supply.empty() && !demand.empty()) {
			ll row1 = supply.front(), row2 = demand.front();
			supply.pop();
			demand.pop();
			cnts[row1]--;
			cnts[row2]++;
			ans.push_back({row1+1, row2+1, j+1});
		}
	}
	bool okay = true;
	for (ll i = 0; i < n; ++i) if (cnts[i] != target) okay = false;
	if (!okay) cout << -1 << "\n";
	else {
		ll len = ans.size();
		cout << len << "\n";
		for (ll i = 0; i < len; ++i) cout << ans[i][0] << " " << ans[i][1] << " " << ans[i][2] << "\n";
	}

}


int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	long long cases = 1;
	cin >> t;
	while (t--) {
		solve(cases);
		cases++;
	}
	return 0;
}